#include "Sort.h"
#include "Stack.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);	
	}
	printf("\n");
}

//void InsertSort(int* a, int n)
//{
//	int i, end;
//	for (i = 1; i < n; i++)
//	{
//		int tmp = a[i];
//		end = i - 1;
//
//		while(a[end] > k && j >= 0)
//		{
//			a[end + 1] = a[end];
//			end--;
//		}
//		a[end + 1] = tmp;
//	}	
//}

//时间复杂度：O(N^2) 经典的等差数列
void InsertSort(int* a, int n)
{
	// 排序，排 n - 1 躺
	for (int i = 0; i < n - 1; i++)
	{
		// 单躺排序
		// [0, end] 有序，把 end + 1 位置的值插入到合适位置
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

// 时间复杂度：
// 预排序：以3为底的对数
// gap为 N/3 , 所以 n - gap 为 2/3 * N
// gap很大时，每次移动 gap 步，最多就移动三次。
// 所以 gap 很大时，大概是 2/3*N * 3 = 2N
// gap很小时（1或2），n - gap 近似为 n，但此时的数组已经接近有序
// 使用插排，只需要走几次循环就能跳出循环了。因此 while循环 近似为O(1)
// 所以 gap 很小时，大概是 N * 1 = N
// 综上，时间复杂度可以大致为 O（log3 N * N）这个量级
void ShellSort(int* a, int n)
{
/*  单躺排序
	int gap = 3;
	for (int j = 0; j < gap; j++)
	{
		for (int i = 0; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
*/
	int gap = n;
	while (gap > 1)
	{
		// 加1的目的是，防止gap大于1小于3的情况，整除后就为0
		// 加1最后可以直接变成插排
		gap = gap / 3 + 1;	
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp > a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}

//时间复杂度：O(N^2) 经典的等差数列  最好的情况：O(N^2)
//对比 插入排序，谁更好？  --- 插入
void SelectSort(int* a, int n)
{
	assert(a);

	int begin = 0, end = n - 1;
	while (begin < end)
	{	
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}
			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);

		//如果begin和maxi重叠，那么在begin和mini交换后
		//begin被换到了mini的位置，也就是maxi位置变成了mini的位置
		//因此需要修正一下maxi的位置
		if (begin == maxi)
		{
			maxi = mini;
		}

		Swap(&a[end], &a[maxi]);
		++begin;
		--end;
	}
}


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


void AdjustDwon(int* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		// 选出左右孩子中小/大的那个
		if (child + 1 < size && a[child + 1] > a[child])
		{
			++child;
		}

		// 孩子跟父亲比较
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 降序 -- 建小堆
// 升序 -- 建大堆
void HeapSort(int* a, int n)
{
	// 建堆方式2：O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDwon(a, n, i);
	}

	// O(N*logN)
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		--end;
	}
}

//时间复杂度：O(N^2) 最好的情况：O(N)
//对比 插入排序，谁更好？  --- 插入
void BubbleSort(int* a,int n)
{
	assert(a);

	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - 1 - i; j++)
		{
			if (a[j + 1] < a[j])
			{
				Swap(&a[j + 1], &a[j]);
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}


//void QuickSort(int* a, int begin, int end)
//{
//	assert(a);
//
//	//区间只有一个指，或是区间不存在，则不需要处理
//	if (begin >= end)
//	{
//		return;
//	}
//
//	//结论：左边做 key，右边（找小）先走
//	int left = begin, right = end;
//	int keyi = left;
//	while (left < right)
//	{
//		// 右边先走，找小
//		// 情况 1  因为 key 为最左值，而右边是找到比 key 小的就停下来
//		// 只有让右边先走，才能保证最后 left == right 时
//		// 所在位置的值比 key 要小，然后与 key 交换，才能保证左边都小于 key
//		// 情况 2  R先走，但没有找到比 key 小的值，没有停下来，直到与L相遇
//		// ① L没有移动过。那么 key 就是 L，而 key 右边的都比 key大
//		//    此情况不影响，就是 key 和自己交换而已
//		// ② L移动过。那么在R移动之前，L已经与R进行一次交换了，所以L所在的位置的值，
//		//    一定是比 key要小的，所以 R 一直找小，直到遇到 key 也无妨。
//		while (left < right && a[right] >= a[keyi])
//		{
//			right--;
//		}
//		// 左边先走，找大
//		while (left < right && a[left] <= a[keyi])
//		{
//			left++;
//		}
//		Swap(&a[left], &a[right]);
//	}
//	Swap(&a[keyi], &a[right]);
//	keyi = left;
//
//	// 分治思想，先排左边，再排右边
//	// [begin, keyi - 1] keyi [keyi +1, end]
//	QuickSort(a, begin, keyi - 1);
//	QuickSort(a, keyi + 1, end);
//}

int GetMidIndex(int* a, int begin, int end)
{
	int mid = (begin + end) / 2;
	
	if (a[begin] < a[mid])
	{
		// begin < mid < end
		if (a[mid] < a[end])
		{
			return mid;
		}
		// begin < end < mid
		else if (a[begin] < a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}

	}
	else   //(a[begin] >= a[mid])
	{
		if (a[mid] > a[end])
		{
			return mid;
		}
		else if (a[begin] > a[end])
		{
			return end;
		}
		else
		{
			return begin;
		}
	}
}

/* hoare版本 */
int PartSort1(int* a, int begin, int end)
{
	int left = begin, right = end;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		// 左边先走，找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		Swap(&a[left], &a[right]);
	}
	Swap(&a[keyi], &a[right]);
	keyi = left;
	
	return keyi;
}

/* 挖坑法 */
int PartSort2(int* a, int begin, int end)
{
	int left = begin, right = end;
	int piti = begin;
	int key = a[begin];
	while (begin < end)
	{
		while (begin < end && a[end] >= key)
		{
			--end;
		}
		a[begin] = a[end];
		piti = end;

		while (begin < end && a[begin] <= key)
		{
			++begin;
		}
		a[end] = a[begin];
		piti = begin;
	}
	// bgein 与 end 相遇时，当前位置就是坑位。
	a[piti] = key;

	return piti;
}


/* 前后指针版 */
int PartSort3(int* a, int begin, int end)
{
	int prev = begin;
	int cur = prev + 1;
	int keyi = begin;

	//int midi = GetMidIndex(a, begin, end);
	//Swap(&a[keyi], &a[midi]);

	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}

		++cur;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	
	return keyi;
}

//时间复杂度：O(logN*N)
void QuickSort(int* a, int begin, int end)
{
	assert(a);

	if (begin >= end)
	{
		return;
	}

	//if (end - begin > 10)
	{
		//int keyi = PartSort1(a, begin, end);
		//int keyi = PartSort2(a, begin, end);
		int keyi = PartSort3(a, begin, end);

		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	//else
	//{
		//InsertSort(a + begin, end - begin + 1);
	//}
}

// 快排递归改非递归:
// 递归大问题，极端场景下，深度太深，会导致栈溢出
// 1、直接改循环 -- 比如斐波那契数列、归并排序
// 2、使用数据结构栈 模拟递归过程
void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	StackInit(&st);

	StackPush(&st, end);
	StackPush(&st, begin);

	while (!StackEmpty(&st))
	{
		int left = StackTop(&st);
		StackPop(&st);

		int right = StackTop(&st);
		StackPop(&st);

		int keyi = PartSort3(a, left, right);

		if (keyi + 1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyi + 1);
		}

		if (left < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, left);
		}
	}

	StackDestory(&st);
}

void _MergeSort(int* a, int begin, int end, int* tmp)
{
	if (begin >= end)
	{
		return;
	}

	int mid = (begin + end) / 2;
	
	//分治递归 [begin, mid] [mid + 1, end]
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//归并 [begin, mid] [mid + 1, end]
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	int i = begin1;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}

	//for (i = begin; i < end; i++)
	//{
	//	a[i] = tmp[i];
	//}
	memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}

//时间复杂度：O(N*logN）
//空间复杂度：O(N)
void MergeSort(int* a, int n)
{
	assert(a);

	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("MergeSort::malloc");
		return;
	}

	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("MergeSort::malloc");
		return;
	}

	int gap = 1;
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2 * gap)
		{
			// 每次划分为两个区间进行归并
			// [i, i + gap - 1] [i + gap, i + 2 * gap -1]
			int begin1 = i, end1 = i + gap - 1;
			int begin2 = i + gap, end2 = i + 2 * gap - 1;
			int j = begin1;
			int sz = end2 - begin1 + 1;
			 
			/* 非递归难点分析：
			 因为归并完成之后，gap每次都是乘2
			 所以如果数组个数不是2的次方倍，就会出现越界
			 ① 比如数组个数为9时，第一趟归并时，最后是 [8,8] [9,9]，最后一组的第二个区间就越界了
			 第二趟归并时，[0,1][2,3]--[4,5][6,7]--[8,9][10,11]，最后一组从 end1 位置开始就越界了
			 第三趟归并时，[0,3][4,7]--[8,11][12,15],最后一组从 begin1 之后的位置就越界了
			 第四躺归并时，[0,7][8,15]
			 ② 比如数组个数为10时，第一趟归并时，最后是 [8,8] [9,9]，第一组没问题
			 第二趟归并时，[0,1][2,3]--[4,5][6,7]--[8,9][10,11]，最后一组从 begin2 位置开始就越界了
			 第三趟归并时，[0,3][4,7]--[8,11][12,15],最后一组从 begin1 之后的位置就越界了
			 第四躺归并时，[0,7][8,15]
			
			 综上分析，有两种解决方案
			 1、修正区间
			 2、对越界区间直接不归并，但需要在每一组归并完成之后，及时拷贝
			    不能在一趟之后在进行整体拷贝，否则会出现，越界的区间没有存储到 tmp 数组
			    该位置为随机值，拷贝回原数组，覆盖了原数组该位置的值  */
			
			// 第一种：修正区间 
			if (end1 >= n)
			{
				end1 = n - 1;

				//如果是end1开始就越界，那么将第二个区间修正为不存在的区间
				begin2 = n;
				end2 = n - 1;
			}
			else if (begin2 >= n)
			{
				begin2 = n;
				end2 = n - 1;
			}
			else if (end2 >= n)
			{
				end2 = n - 1;
			}

/*          
			第二种：对越界区间直接不归并 
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			//如果仅是第二个区间的右区间越界，需要修正
			else if (end2 >= n)
			{
				end2 = n - 1;
			}
 */
				
			//归并
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] < a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}

/*			
			对应第二种解决方案 
			memcpy(a + i, tmp + i, sizeof(int) * sz);
*/

		}

		//拷贝回原数组
		memcpy(a, tmp, sizeof(int) * n);
		//因为一组数据是两个区间进行归并，每个区间为一个gap
		//所以归并完成一组之后，往后跳两个gap
		gap *= 2;
	}

	free(tmp);
}

//时间复杂度：O(max(range,N))
//空间复杂度：O(range)
//计数排序局限性:
//1、只适用整数
//2、如果数据范围很大，空间复杂度高，相对不合适。
void CountSort(int* a, int n)
{
	int min = a[0], max = a[0];

	//找最大和最小值
	for (int i = 1; i < n; ++i)
	{
		if (a[i] < min)
			min = a[i];
		if (a[i] > max)
			max = a[i];
	}

	//计算数据范围
	int range = max - min + 1;
	int* count = (int*)calloc(range,sizeof(int));
	if (count == NULL)
	{
		perror("CountSort::malloc");
		return;
	}

	//计数
	for (int i = 0; i < n; ++i)
	{
		count[a[i] - min]++;
	}

	//回写 - 排序
	int j = 0;
	for (int i = 0; i < range; ++i)
	{
		while (count[i]--)
		{
			a[j++] = i + min;
		}
	}
}